Foundries often restrict electronic design implementations to a limited number of routing track arrangements, each of which may only take on interconnect segments having width values from a discrete set of legal widths that may be made available in the process Design Rule Manual (DRM) in an effort accommodate complex design rules for advanced process nodes (e.g., 14-nm, 10-nm or below). Furthermore, in order to facilitate multiple-patterning lithographic processes (e.g., SADP or self-aligned double-patterning, SATP or self-aligned triple patterning, LELELE or lithography-etch-lithography-etch-lithography-etch, etc.), foundries may further impose additional constraints on the availability of wire widths that are associated with routing tracks. For example, after a first routing track is chosen and assigned a mask color (e.g. B for Blue) for a particular interconnect segment having a specific width, the next routing track may need to be assigned a different color (e.g., C for Cyan), and may only accept a wire having one of a discrete set of legal width values, where the discrete set of legal width values is in turn a function of the legal width associated with the preceding B routing track.
An electronic design may thus correspond to and include about, for example, a dozen different wire widths, and the routing tracks for routing the electronic design may thus be associated with as many legal widths. Any attempt to manually figure out which routing track associated with a permissible width can immediately neighbor another routing track associated with another permissible width is nearly impossible due to the sheer number of different possible legal combinations of routing tracks, especially in light of the extremely complex design rules that govern what track patterns are deemed legal. Therefore, generating a legal track pattern including a plurality of tracks associated with some legal widths is nearly impossible to be performed manually, especially when an electronic design includes more than just a handful of legal or permissible widths. Repetitive track patterns may further exacerbate the complexity in that each track pattern needs to comply with governing design rules and constraints for track patterns, and the repetitive track patterns as a whole also needs to comply with the same set of governing design rules and constraints. Any additions or removal of one or more tracks to a track pattern may propagate throughout the repetitive track patterns, even if a single track pattern may comply with all the pertinent design rules and constraints.
The interplay among complex design rules, the permissible, legal track patterns, and the addition, removal, or modification of an existing design component further complicates the solution finding process to an inextricable extent. A track pattern may be deemed legal if the group of one or more routing tracks in the track pattern complies with various design rules governing which arrangements or sequences of routing track associated with their respective widths are permitted. For example, a design may prohibit arranging a thin wire segment having a width of w1 immediately adjacent to a thick or fat wire segment having a width of w2 in any track pattern. Given this design rule, any track patterns having such an arrangement of two immediately neighboring tracks associated with w1 with w2 violate this design rule and will thus be considered illegal. During the physical design implementation stage, a change may be introduced into an electronic design by, for example, adding, removing, or modifying one or more shapes (e.g., wire segments) in a region of an electronic design. Such a change may be introduced manually by a designer during an interactive editing session or by an electronic design automation (EDA) tool. For example, a designer may insert a second metal shape on a second routing track in a region of an electronic design. The insertion of the second metal shape may leave an unoccupied space between the second metal shape and a preexisting first metal shape implemented along a first routing track.
Assuming the distance between the first metal shape and the second metal shape is the fill distance, the goal is then to find positive definite solutions to a linear Diophantine equation. Depending upon the number of permissible wire widths and the spacing values in an electronic design, the linear Diophantine equation may be solved by using combinatorial optimization techniques such as those used to solve the Knapsack problem in some embodiments. Some other embodiments may utilize a static, predetermined dictionary including permissible legal track patterns that may be looked up for the region at issue. A set of legal track patterns may be identified by considering, for example, the widths of the first shape and the second shape and the fill distance.
Therefore, there exists a need for a method, system, and computer program product for implementing DRC (design rule check) clean multi-patterning process nodes with parallel fills in electronic designs.